package algorithm.sort;

public class MergeSort implements SortAlgorithm {
    @Override
    public void sort(int[] inputArray) {
        mergeSort(inputArray, 0, inputArray.length - 1);
    }

    private void mergeSort(int[] array, int p, int r) {
        if (p >= r) {
            return;
        }

        int q = (p + r) / 2;
        mergeSort(array, p, q);
        mergeSort(array, q + 1, r);
        merge(array, p, q, r);
    }

    private void merge(int[] array, int p, int q, int r) {
        int leftIdx = p;
        int rightIdx = q + 1;
        int tempArrayIdx = 0;
        int[] tempArray = new int[r - p + 1];

        while (leftIdx <= q && rightIdx <= r) {
            if (array[leftIdx] < array[rightIdx]) {
                tempArray[tempArrayIdx++] = array[leftIdx++];
            } else {
                tempArray[tempArrayIdx++] = array[rightIdx++];
            }
        }

        while (leftIdx <= q) {
            tempArray[tempArrayIdx++] = array[leftIdx++];
        }

        while (rightIdx <= r) {
            tempArray[tempArrayIdx++] = array[rightIdx++];
        }

        for (int number : tempArray) {
            array[p++] = number;
        }
    }
}
